package Test.offer;



/**
 * @ClassName P52
 * @Description 寻找链表的公共节点
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/31 11:48
 * @Version 1.0
 */
public class P52 {

    /**
     * 暴力法
     * @param node1
     * @param node2
     * @return
     */
    LinkNode findFirstCommanNode(LinkNode node1, LinkNode node2) {
        if (node1 == null || node2 == null) {
            return null;
        }
        int len1 = getLen(node1);
        int len2 = getLen(node2);

        while (len1 > len2) {
            node1 = node1.next;
            len1--;
        }
        while (len2 > len1) {
            node2 = node2.next;
            len2--;
        }

        while (node1 != null && node2 != null && node1 != node2) {
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }

    private int getLen(LinkNode node) {
        if (node == null) return 0;
        int len = 1;
        while (node.next != null) {
            len++;
            node = node.next;
        }
        return len;
    }

    /**
     * 双指针法
     * @param node1
     * @param node2
     * @return
     */
    LinkNode findFirstCommanNode1(LinkNode node1, LinkNode node2) {
        if (node1 == null || node2 == null) {
            return null;
        }
        LinkNode n1 = node1;
        LinkNode n2 = node2;
        while (n1 != n2) {
            n1 = (n1 != null)?n1.next: node2;
            n2 = (n2 != null)?n2.next: node1;
        }
        return n1;
    }

    class ListNode {
        int val;
        ListNode next;
        ListNode(int v) {
            val = v;
            next = null;
        }
    }

    class LinkNode {
        LinkNode next;
        int val;
    }
}
